package formal.tree.bst;

import java.util.*;

/**
 * 二叉树的最近公共祖先
 * todo E_235是二叉搜索树，这里只是二叉树
 *
 * @author DengYuan2
 * @create 2021-01-23 21:33
 */
public class M_236 {
    public static void main(String[] args) {
        Integer[] a = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4, null, null, null, null};
        TreeNode treeNode = TreeNode.generateTree(a);
        TreeNode res = lowestCommonAncestor(treeNode, new TreeNode(0), new TreeNode(6));
        System.out.println(res);
    }

    /**
     * 不会-官方-先找出每个节点的父节点，然后把p的所有父节点（指每个父节点的父节点）找出来，与q的所有父节点比较
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<Integer, TreeNode> parent = new HashMap<>(16);
        findParent(root,parent);
        //找出所有p的父节点,也要包括自己哦
        List<Integer> pp = new ArrayList<>();
        while (p!=null){
            pp.add(p.val);
            p=parent.get(p.val);
        }
        while (q!=null){
            if (pp.contains(q.val)){
                return q;
            }
            q=parent.get(q.val);
        }
        return null;
    }

    public static void findParent(TreeNode root,HashMap<Integer,TreeNode> map){
        if (root==null){
            return;
        }
        if (root.left!=null){
            map.put(root.left.val,root);
            findParent(root.left,map);
        }
        if (root.right!=null){
            map.put(root.right.val,root);
            findParent(root.right,map);
        }
    }

    /**
     * 官方-大神-递归-思想还是不太懂啊
     * @param root
     * @param p
     * @param q
     * @return
     */
    public static TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q){
        if (root==null || root==p||root==q){
            return root;
        }
        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);
        if (left==null){
            return right;
        }
        if (right==null){
            return left;
        }
        return root;
    }
}
